


def parse1(s):
    acc = [[]]
    for ch in s:
        if ch == '(':
            acc.append([])
        elif ch == ')':
            if len(acc) == 1:
                raise Exception("more ')'")
            last = acc.pop()
            acc[-1].append(last)
        else:
            acc[-1].append(ch)
    if len(acc) != 1:
        raise Exception("less ')'")
    return acc.pop()

class LineMach:
    def __init__(self):    # 不用处理错误，直接中断+err置1
        self.rules = []

    def reg(self, state, a):
        def g(f):
            self.rules.append(((state, a), f))
        return g

    def run(self, data, debug=True):
        state = Ss()
        data += ["end"]
        for a in data:
            state = self.reduction(state, a, debug)
        assert isinstance(state, Xs)
        #print(repr3(state.x))
        return state.x

    def reduction(self, state, a, debug):
        for (t1, t2), f in self.rules:
            if match(state, t1) and match(a, t2):
                if debug:
                    print("match from", state, a)
                    print( "match", repr2(t1), repr2(t2))
                r = f(state, a)
                if debug:
                    print("to", r)
                return r
        else:
            print("err1", state, repr(a))
            raise Exception("无可匹配的规则")

lm = LineMach()

class State:
    def __repr__(self):
        return f"<{type(self).__name__}>"


class Ss(State):
    def __init__(self):
        pass


class Xs(State):
    def __init__(self, x):
        self.x = x


class Fs(State):
    def __init__(self, last, f, k):
        assert not isinstance(last, Fxs)
        self.last = last
        self.f = f
        self.k = k      # 左右结合权重

    def eat(self, x):
        return Fxs(self.last, self.f, x, self.k)

class Fxs(State):
    def __init__(self, last, f, x, k):
        assert not isinstance(last, Fxs)
        self.last = last

        self.f = f
        self.x = x
        self.k = k      # 左右结合权重

    def sto(self):
        return Fs(self.last, self.f + [self.x], self.k)

    def spew(self):
        return Fs(self.last, self.f, self.k), self.x


def repr2(pattern):
    if isinstance(pattern, type):
        return pattern.__name__
    elif isinstance(pattern, list):
        s = ', '.join(repr2(x) for x in pattern)
        return "[" + s + "]"
    elif callable(pattern):
        return pattern.__name__
    else:
        return pattern.__repr__()

def repr3(tree):
    if isinstance(tree, list):
        s = ', '.join(repr3(x) for x in tree)
        return "[" + s + "]"
    elif isinstance(tree, str):
        return tree
    else:
        #print(type(tree))
        return repr(tree)


def match(x, pattern):
    if isinstance(pattern, type):
        return isinstance(x, pattern)
    elif isinstance(pattern, list):
        flag = False
        for p2 in pattern:
            if match(x, p2):
                flag = True
                break
        return flag
    elif callable(pattern):
        return pattern(x)
    else:
        return x == pattern


table_op2 = {}
table_head = {}
table_tail = {}

table_head['x'] = 5
table_head['y'] = 5
table_head['z'] = 5
table_head['u'] = 5
table_head['v'] = 5
table_head['w'] = 5
table_head['.'] = 8
greedy = ['x', 'y', 'z', 'u', 'v', 'w']
table_op2['+'] = 3
table_op2['-'] = 3
table_op2['%'] = 4
table_op2['|'] = 4
table_op2['^'] = 4.1
table_tail['`'] = 7
table_tail['~'] = 7

HEAD = [*table_head.keys()]
OP2 = [*table_op2.keys()]
TAIL = [*table_tail.keys()]

@lm.reg(Ss, HEAD)
def f(ss, a):
    return Fs(None, [a], table_head[a])

#避开Xs处理，视为Fxs
@lm.reg(Ss, list)
def f(ss, a):
    return Fxs(None, ['0'], parse2(a), 15)


@lm.reg(Ss, list('0123456789'))
def f(ss, a):
    return Fxs(None, ['0'], a, 15)


@lm.reg(Fs, list("123456789"))
def f(fs, a):
    # ~ print("start", fs.f)
    return fs.eat(a)


@lm.reg(Fxs, list("123456789"))
def f(fxs, a):
    if fxs.f[0] in greedy:
        if len(fxs.x) <= 2:
            return fxs.sto().eat(a)
        else:
            raise Exception("x1111")
    else:
        fs = fxs.last
        assert fs.f[0] in greedy
        return fs.eat(fxs.f + [fxs.x]).sto().eat(a)


@lm.reg(Fxs, OP2)
def f(fxs, a):
    opk = table_op2[a]
    if fxs.k >= opk:
        #危险代码
        while fxs.last is not None and fxs.last.k >= opk:
            fs = fxs.last
            fxs = Fxs(fs.last, fs.f, fxs.f + [fxs.x], fs.k)
        return Fs(fxs.last, [a, fxs.f + [fxs.x]], opk)
    else:
        loser = Fs(fxs.last, fxs.f, fxs.k)
        return Fs(loser, [a, fxs.x], opk)


@lm.reg(Fxs, TAIL)
def f(fxs, a):
    opk = table_tail[a]
    if fxs.k >= opk:    # 不优先结合
        #print('he1', fxs, fxs.f, fxs.x)
        while True:
            fs = fxs.last
            b = fxs.f + [fxs.x]
            #print(9, fs, fs.f, b)
            if fs is None or fs.k < opk:
                break
            else:
                fxs = fs.eat(b)
        return fs.eat([a, b])
    else:   # 优先结合
        fs, b = fxs.spew()
        return fs.eat([a, b])
        #return Fxs(fxs.last, fxs.f, [a, fxs.x], fxs.k)


@lm.reg(Fs, list)
def f(fs, a):
    a = parse2(a)
    return fs.eat(a)


@lm.reg(Fs, HEAD)
def f(fs, a):
    return Fs(fs, [a], table_head[a])


@lm.reg(Fxs, HEAD)
def f(fxs, a):
    assert a not in greedy
    print('here')

    if fxs.f[0] in greedy:
        #fxs=u1
        #这是贪婪项归并标准代码，fx转f
        eater = fxs.sto()
        return Fs(eater, [a], table_head[a])
    else:
        #fxs=u.
        eater = fxs.last # 这次是个fs
        eater = eater.eat(fxs.f + [fxs.x])
        eater = eater.sto()
        return Fs(eater, [a], table_head[a])

@lm.reg(Fxs, "end")
def f(fxs, a):
    while fxs.last is not None:
        fs = fxs.last
        fxs = Fxs(fs.last, fs.f, fxs.f + [fxs.x], fs.k)
    return Xs(fxs.f + [fxs.x])


from itertools import product

def mean(x, acc=0):
    if x == 1:
        return range(1)
    elif isinstance(x, str):
        x = int(x)
        hx = int((x /2 - 0.5) // 1)
        return range(-hx+acc, x-hx+acc)
    elif isinstance(x, list) and x[0] == '`':
        return mean(x[1], acc+1)
    elif isinstance(x, list) and x[0] == '~':
        return mean(x[1], acc-1)
    else:
        raise Exception("未知格式 "+repr(x))

def mean2(x):
    if x == 1:
        return (0, None)    # 0用来标记没有输入
    elif isinstance(x, str):
        x = int(x)
        return (x, None)
    elif isinstance(x, list) and x[0] == '.':
        assert isinstance(x[1], str)
        return (-int(x[1]), None)
    elif isinstance(x, list) and x[0] == '~':
        return (mean2(x[1])[0], '~')
    else:
        raise Exception("未知格式 "+repr(x))

def box_eval(tree):
    if isinstance(tree, str):
        return int(tree)
    elif tree[0] == 'x':
        body = tree[1:]
        if len(body) == 1:
            x, = body
            return list(product(mean(x), range(1), range(1)))
        elif len(body) == 2:
            y, z = body
            return list(product(range(1), mean(y), mean(z)))
        elif len(body) == 3:
            x, y, z = body
            return list(product(mean(x), mean(y), mean(z)))
    elif tree[0] == 'y':
        body = tree[1:]
        if len(body) == 1:
            y, = body
            return list(product(range(1), mean(y), range(1)))
        elif len(body) == 2:
            x, z = body
            return list(product(mean(x), range(1), mean(z)))
        elif len(body) == 3:
            y, x, z = body
            return list(product(mean(x), mean(y), mean(z)))
    elif tree[0] == 'z':
        body = tree[1:]
        if len(body) == 1:
            z, = body
            return list(product(range(1), range(1), mean(z)))
        elif len(body) == 2:
            x, y = body
            return list(product(mean(x), mean(y), range(1)))
        elif len(body) == 3:
            z, x, y = body
            return list(product(mean(x), mean(y), mean(z)))
    elif tree[0] == 'u':
        body = tree[1:]
        if len(body) == 1:
            (x,), y, z = body, 1, 1
        elif len(body) == 2:
            (y, z), x = body, 1
        elif len(body) == 3:
            x, y, z = body
        return Vech(mean2(x), mean2(y), mean2(z))
    elif tree[0] == 'v':
        body = tree[1:]
        if len(body) == 1:
            (y,), x, z = body, 1, 1
        elif len(body) == 2:
            (x, z), y = body, 1
        elif len(body) == 3:
            y, x, z = body
        return Vech(mean2(x), mean2(y), mean2(z))
    elif tree[0] == 'w':
        body = tree[1:]
        if len(body) == 1:
            (z,), x, y = body, 1, 1
        elif len(body) == 2:
            (x, y), z = body, 1
        elif len(body) == 3:
            z, x, y = body
        return Vech(mean2(x), mean2(y), mean2(z))

    elif tree[0] == '+':
        a1, a2 = tree[1:]
        a1 = box_eval(a1)
        a2 = box_eval(a2)
        acc = a1.copy()
        for pos in a2:
            if pos not in a1:
                acc.append(pos)
        return acc
    elif tree[0]  == '-':
        a1, a2 = tree[1:]
        a1 = box_eval(a1)
        a2 = box_eval(a2)
        acc = []
        for pos in a1:
            if pos not in a2:
                acc.append(pos)
        acc.sort()
        return acc
    elif tree[0] == '0':
        return box_eval(tree[1])
    elif tree[0] == '.':
        assert tree[1].isdigit()
        return -int(tree[1])
    elif tree[0] == '^':
        a = box_eval(tree[1])
        b = box_eval(tree[2])
        if isinstance(a, tuple):
            return a + (b,)
        else:
            return (a, b)
    elif tree[0] == '%':
        a = box_eval(tree[1])
        b = box_eval(tree[2])
        assert isinstance(b, tuple) and len(b) > 1
        n = b[0]
        if type(n) is int:  # 非方阵列，数量在前
            v = b[1]
            assert n > 0
            v = v.cute()
            dl = []
            if n % 2 == 1:
                hn = n // 2
                for d in range(-hn, hn+1):
                    dl.append(v * d)
            else:
                hv = v * 0.5
                hv = Vec(ceil(hv.x), ceil(hv.y), ceil(hv.z))
                hn = n // 2
                for d in range(-hn, hn):
                    dl.append(v * d + hv)
            acc = []
            for p in a:
                for d in dl:
                    acc.append(tuple(Vec(*p)+d))
            return acc
        elif type(n) is Vec:    # 方形阵列， 偏移在前
            v = n
            vv = v.cute()
            nl = b[1:]
            print(nl)
            con = (int(v.x != 0), int(v.y != 0), int(v.z != 0))
            cond = (int(v.dx == '~'), int(v.dy == '~'), int(v.dz == '~'))
            print(con, cond)
            if con == (1, 1, 1):
                if cond == (1 ,1, 1):
                    l = [vv]
                elif cond == (1, 1, 0):
                    l = [vv* Vec(1, 1 ,0), vv * Vec(0, 0, 1)]       # 注意要和参数顺序一致
                elif cond == (0, 1, 1):
                    l = [vv * Vec(1, 0, 0), vv* Vec(0, 1 ,1)]
                elif cond == (1, 0, 1):
                    l = [vv* Vec(1, 0 ,1), vv * Vec(0, 1, 0)]
                else:
                    l = [vv* Vec(1, 0 ,0), vv * Vec(0, 1, 0), vv * Vec(0, 0, 1)]
            elif con == (1, 1, 0):
                if cond == (1, 1, 0):
                    l = [vv]
                else:
                    l = [vv * Vec(1, 0, 0), vv* Vec(0, 1, 0)]
            elif con == (0, 1, 1):
                if cond == (0, 1, 1):
                    l = [vv]
                else:
                    l = [vv * Vec(0, 1, 0), vv* Vec(0, 0, 1)]
            elif con == (1, 0, 1):
                if cond == (1, 0, 1):
                    l = [vv]
                else:
                    l = [vv* Vec(1, 0 ,0), vv * Vec(0, 0, 1)]
            elif con in [(1, 0, 0), (0, 1, 0), (0, 0, 1)]:
                l = [vv]
            else:
                raise Exception("未知方形阵列模式")
            assert len(nl) == len(l)
            temp = []
            for v, n in zip(l, nl):
                assert isinstance(n, int) and n > 0
                temp.append([v * i for i in mean(str(n))])
            fin = []
            for pl in product(*temp):
                fp = sum(pl, Vec(0, 0, 0))
                for basep in a:
                    fin.append(tuple(Vec(*basep)+fp))
            return fin


    elif tree[0] == '|':
        a = box_eval(tree[1])
        b = box_eval(tree[2])
        assert isinstance(b, Vec)
        # 协变

        v = b.cute()
        temp = [Vec(*p) + v for p in a]     # 先位移


        # u3~33~
        con = (int(b.x != 0), int(b.y != 0), int(b.z != 0))
        cond = (int(b.dx == '~'), int(b.dy == '~'), int(b.dz == '~'))

        if con == (1, 1, 1):
            if cond == (1, 1, 1):       # 全部协变
                k = [Vec(1, 1, 1), Vec(-1, -1, -1)]
            elif cond == (1, 1, 0):
                k = pm([Vec(1, 1, 1), Vec(-1, -1, 1)], [Vec(1, 1, 1), Vec(1, 1, -1)])
            elif cond == (0, 1, 1):
                k = pm([Vec(1, 1, 1), Vec(1, -1, -1)], [Vec(1, 1, 1), Vec(-1, 1, 1)])
            elif cond == (1, 0, 1):
                k = pm([Vec(1, 1, 1), Vec(-1, 1, -1)], [Vec(1, 1, 1), Vec(1, -1, 1)])
            else:   # 没有协变
                k = pm(pm([Vec(1, 1, 1), Vec(-1, 1, 1)], [Vec(1, 1, 1), Vec(1, -1, 1)]), [Vec(1, 1, 1), Vec(1, 1, -1)])
        elif con == (1, 1, 0):
            if cond == (1, 1, 0):
                k = [Vec(1, 1, 1), Vec(-1, -1, 1)]
            else:
                k = pm([Vec(1, 1, 1), Vec(-1, 1, 1)], [Vec(1, 1, 1), Vec(1, -1, 1)])
        elif con == (1, 0, 1):
            if cond == (1, 0, 1):
                k = [Vec(1, 1, 1), Vec(-1, 1, -1)]
            else:
                k = pm([Vec(1, 1, 1), Vec(-1, 1, 1)], [Vec(1, 1, 1), Vec(1, 1, -1)])
        elif con == (0, 1, 1):
            if cond == (0, 1, 1):
                k = [Vec(1, 1, 1), Vec(1, -1, -1)]
            else:
                k = pm([Vec(1, 1, 1), Vec(1, -1, 1)], [Vec(1, 1, 1), Vec(1, 1, -1)])
        elif con == (1, 0, 0):
            k = [Vec(1, 1, 1), Vec(-1, 1, 1)]
        elif con == (0, 1, 0):
            k = [Vec(1, 1, 1), Vec(1, -1, 1)]
        elif con == (0, 0, 1):
            k = [Vec(1, 1, 1), Vec(1, 1, -1)]
        else:
            raise Exception("未知镜像方式")


        acc = []
        for p in temp:
            for j in k:
                r = p * j
                if r not in acc:
                    acc.append(tuple(r))
        acc.sort()
        return acc


    else:
        raise Exception(repr(tree))

def parse2(l):
    return lm.run(l, debug=False)
    # ~ return lm.run(l, debug=True)

from dataclasses import dataclass

@dataclass
class Vec:
    x: int
    y: int
    z: int
    dx: object = None # decorator
    dy: object = None
    dz: object = None

    def __add__(a, b):
        return Vec(a.x + b.x, a.y + b.y, a.z + b.z)

    def __sub__(a, b):
        return Vec(a.x - b.x, a.y - b.y, a.z - b.z)

    def __mul__(a, k):
        if isinstance(k, Vec):
            return Vec(a.x * k.x, a.y * k.y, a.z * k.z)
        else:
            return Vec(a.x * k, a.y * k, a.z * k)

    def __iter__(a):
        return iter((a.x, a.y, a.z))

    @staticmethod
    def _h(x):
        if x == 0:
            return 0
        elif x > 0:
            return x -1
        else:
            return x + 1

    def cute(a):
        _h = Vec._h
        return Vec(_h(a.x), _h(a.y), _h(a.z))

def pm(l1, l2):     # product vec mul
    acc = []
    for v1 in l1:
        for v2 in l2:
            acc.append( v1 * v2)
    return acc

def Vech(a, b, c):
    x, dx = a
    y, dy = b
    z, dz = c
    return Vec(x, y, z, dx, dy, dz)


from math import ceil

def ana(code):
    r = parse1(code)
    r2 = parse2(r)
    r3 = box_eval(r2)
    if not isinstance(r3, list):
        raise Exception()
    r3.sort()
    return r3

__all__ = ["ana"]

if __name__ == "__main__":
    # ~ code = "x333-(y33-z3)"
    # ~ code = "x3+y3+z3"
    # ~ code = "x333-(x3+y3+z3)"
    code = "x3``3~~3+x1"
    code = 'x1%u3^2%v3^2'
    #code = '1^2^3'
    #code = 'x1'
    # ~ code = '(x2+y2+z2)|u.3.3.3~'
    # ~ code = '(x2+y2+z2)|u.3~.3~.3'
    # ~ code = '(x2+y2+z2)%2^u2'
    code = '(x2+y2+z2)%u33^2^3'
    code = 'u3.33'
    # ~ code = 'x1%2^u3+x1%2^v3'

    # ~ code = "x1+x1+x1"
    # ~ code = "x333-(y33-z3)+x1"
    # ~ code = "x11+(x11-x11)"
    # ~ code = "x333-1"
    # ~ code = "y33"


    r = parse1(code)
    print(r)
    r = parse2(r)
    print(r)

    from tool_treeprint import tree

    def name(o):
        if isinstance(o, (tuple, list)):
            return o[0]
        else:
            return str(o)

    def member(o):
        if isinstance(o, (tuple, list)):
            return list(o[1:])
        else:
            return []

    tree(r, name, member)



    r = box_eval(r)
    try:
        print(len(r))
    except:
        pass
    print(r)
















